extractMax Code Logic

Click on an explanation to see the code for the bubbleDown logic.

• The while loop continues as long as the current node has children to check.
• First, we find the indices of potential children and assume the parent (`index`) is the largest.
• Check if a left child exists and if it's larger than the current largest element.
• Then, check the right child to see if it's even larger.
• If a larger child was found (meaning largest was updated), swap the parent with that largest child.
• If the parent is already larger than both its children, the property is restored for this subtree, and we can exit the loop.

def bubble_down(heap, index):
    last_index = len(heap) - 1
    while True:

        left_child_i = 2 * index + 1
        right_child_i = 2 * index + 2
        largest = index

        # Check if left child exists and is largest
        if left_child_i <= last_index and heap[left_child_i] > heap[largest]:
            largest = left_child_i

        # Check if right child exists and is largest
        if right_child_i <= last_index and heap[right_child_i] > heap[largest]:
            largest = right_child_i

        if largest != index:
            heap[index], heap[largest] = heap[largest], heap[index]
            index = largest
        else:
            break # Heap property is restored